package demo1;

public class DynamicPlanningPractise {
    /**
     * 地下城游戏-优化
     * 时间复杂度O(m*n)
     * 空间复杂度O(m*n)*/
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        //1 创建dp表
        int[][] dp = new int[m+1][n+1];
        //2 初始化
        for(int i = 0; i <= n; i++)
            dp[m][i] = Integer.MAX_VALUE;
        for(int j = 0; j <= m-2; j++)
            dp[j][n] = Integer.MAX_VALUE;
        dp[m-1][n] = 1;
        //3 填表
        for(int i = m-1; i>=0; i--)
            for(int j = n-1; j>=0; j--)
                dp[i][j] = Math.max(1,(Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]));
        return dp[0][0];
    }

    /**
     * 按摩师
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * 多状态dp问题-》此类题目需再深入研究*/
    public int massage(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;//处理边界情况
        //1 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //2 初始化
        f[0] = nums[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            //4 状态转移方程
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //5 返回值
        return Math.max(f[n-1],g[n-1]);
    }
}
